package com.xzz.dp;

/**
 * @author: hhz
 * @create: 2021-12-31 16:25
 * 0-1背包问题
 **/
public class Backpack01 {
    public static void main(String[] args) {
        System.out.println(backpack01(3, 4, new int[]{2, 1, 3}, new int[]{4, 2, 3}));
    }

    public static int backpack01(int n, int w, int wt[], int[] val) {
        //定义： dp[i][j] :前i个物品装入j容量的背包的最大价值
        int[][] dp = new int[n+1][w+1];

        for (int i = 1; i < n+1; i++) {
            for (int j = 1; j < w+1; j++) {
                //判断当前容量j-wt[i-1]还能不能装的下当前物品
                if(j-wt[i-1]<0){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = Math.max(dp[i-1][j-wt[i-1]]+val[i-1],dp[i-1][j]);
                }
            }
        }
        return dp[n][w];
    }
}
